package november.sort;

import sort.Test;

import java.util.Arrays;

/**
 * @author huangxin
 * @date 2019/11/19-17:41
 */
public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--) {
            //n/2-1   倒数第二层最右边的节点开始
            heapify(arr, n, i);
        }

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    static void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // left = 2*i + 1
        int right = 2 * i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        //如果largest!=root(i)节点,交换位置
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            //递归比较子树
            heapify(arr, n, largest);
        }
    }


    // Driver program
//    public static void main(String args[]) {
//        int[] arr = new int[20];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random() * 800000);
//        }
//        sort(arr);
//
//        System.out.println("Sorted array is");
//        System.out.println(Arrays.toString(arr));
//    }

    public static void main(String[] args) {
        int[] arr = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000000);
        }
//        int[] arr = {2, 5, 6, 1, 123, 9, 1, 12, 7};
        long timeMillis1 = System.currentTimeMillis();
        sort(arr);
        long timeMillis2 = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println(timeMillis2 - timeMillis1);
    }
//
//    /**
//     * @param arr 排序的数组
//     */
//    public static void heapSort(int arr[]) {
////        for (int i = 0; i < arr.length - 1; i++) {
////
////            //最后一个非叶子节点  (arr.length - i)表示递减的数组
////            int index = (arr.length - i) / 2 - 1;
////            while (true) {
////
////                int left = 2 * index + 1;//左边节点
////                int right = 2 * index + 2;//右边节点
////
////                //比较的元素下标, 先左右两个子节点比较, 大的那个再跟父节点比较
////                int childIndex;
////                if (right < arr.length - i - 1) {
////                    //比较左右节点
////                    if (arr[left] > arr[right]) {
////                        childIndex = left;
////                    } else {
////                        childIndex = right;
////                    }
////                } else {
////                    //如果没有右节点,直接用左节点做比较
////                    childIndex = left;
////                }
////
////
////                //父节点和子节点比较(上下节点比较)
////                if (arr[index] < arr[childIndex]) {
////                    //交换
////                    int temp = arr[index];
////                    arr[index] = arr[childIndex];
////                    arr[childIndex] = temp;
////
////
////                }
////
////                if (index <= 0) {
////                    break;
////                }
////                //继续向上比较
////                index = (index - 1) / 2;
////            }
////
////            int temp = arr[0];
////            arr[0] = arr[arr.length - i - 1];
////            arr[arr.length - i - 1] = temp;
////        }
//
//        for (int i = arr.length / 2 - 1; i >= 0; i--) {
//            adjustHeap(arr, i, arr.length);
//        }
//
//        for (int i = arr.length - 1; i > 0; i--) {
//            int temp = arr[i];
//            arr[i] = arr[0];
//            arr[0] = temp;
//            adjustHeap(arr, 0, i);
//        }
//    }
//
//
//    /**
//     * @param arr    待调整的数组
//     * @param i      非叶子节点在数组中的索引
//     * @param length 表示对当前数组的多少个元素进行调整
//     */
//    public static void adjustHeap(int[] arr, int i, int length) {
//        //非叶子节点
//        int temp = arr[i];
//
//        //j = j * 2 + 1循环往左子节点比较
//        for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
//            //arr[j]左节点,arr[j+1]右节点
//            if (j + 1 < length && arr[j] < arr[j + 1]) {
//                j++;//指向右节点
//            }
//
//            //如果子节点>父节点
//            if (arr[j] > temp) {
//                arr[i] = arr[j];
//                i = j;//指向k，继续循环比较
//            } else {
//                break;
//            }
//        }
//
//        arr[i] = temp;
//    }

}
